// https://www.lintcode.com/problem/search-for-a-range/my-submissions?_from=ladder&&fromId=6

class Solution {
public:
    /**
     * @param A: an integer sorted array
     * @param target: an integer to be inserted
     * @return: a list of length 2, [index1, index2]
     */
     
    // 如果target构成的range比较长，用两次二分查找，返回两个边界

    vector<int> searchRange(vector<int> &A, int target) {
        vector<int> result(2, -1);
        if (A.empty()) 
        {
            return result;
        }
        int low = 0;
        int high = A.size() - 1;
        while (low + 1 < high)
        {
            int mid = (high - low) / 2 + low;
            if (A[mid] < target) low = mid;
            else if (A[mid] >= target) high = mid;
        }
        int start;
        if (A[low] == target) start = low;
        else if (A[high] == target) start = high;
        else return result;
        result[0] = start;
        while (A[start] == target) start++;
        result[1] = --start;
        return result;
    }
};